import java.util.*;

public class TreeList {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        inorder(root,res);
        return res;
    }

    private void inorder(TreeNode root, List<Integer> res) {
        if(root!=null){
            inorder(root.left,res);
            res.add(root.val);
            inorder(root.right,res);
        }else {
            return;
        }
    }



    public List<List<Integer>> levelOrder(TreeNode root,int lenth,List<List<Integer>> result) {
        if(root!=null){
            result.get(lenth).add(root.val);
            lenth++;
            result=levelOrder(root.left,lenth,result);
            result=levelOrder(root.right,lenth,result);
        }
        return result;
    }
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=1+maxDepth(root.left);
        int right=1+maxDepth(root.right);
        return left>right?left:right;
    }


    public void connect(TreeLinkNode root) {
        if(root==null) return;
        Queue<TreeLinkNode> queue=new LinkedList<>();
        queue.add(root);
        while (queue.size()!=0){
            int len=queue.size();
            for(int i=0;i<len-1;i++){
                TreeLinkNode t=queue.poll();
                t.next=queue.peek();
                if(t.left!=null) queue.add(t.left);
                if(t.right!=null) queue.add(t.right);
            }
            TreeLinkNode t=queue.poll();
            t.next=null;
            if(t.left!=null) queue.add(t.left);
            if(t.right!=null) queue.add(t.right);
        }

    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> node=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null) return res;
        queue.add(root);
        int index=0;
        while (queue.size()!=0){
            int size=queue.size();
            node=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode t=queue.poll();
                node.add(t.val);
                if(t.left!=null) queue.add(t.left);
                if(t.right!=null) queue.add(t.right);
            }
            if(index%2==1){
                Collections.reverse(node);
            }
            res.add(node);
            index++;
        }
        return res;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len=preorder.length;
        if(len==0){
            return null;
        }else {
            int num=preorder[0];
            TreeNode root=new TreeNode(num);
            int i=0;
            for(;i<len;i++){
                if(inorder[i]==num)break;
            }
            int beforelen=i;
            int []bp=new int[beforelen];
            int []bi=new int[beforelen];
            for(int a=0;a<beforelen;a++){
                bp[a]=preorder[a+1];
                bi[a]=inorder[a];
            }
            root.left=buildTree(bp,bi);
            int []ap=new int[len-beforelen-1];
            int []ai=new int[len-beforelen-1];
            for(int a=beforelen+1;a<len;a++){
                ap[a-beforelen-1]=preorder[a];
                ai[a-beforelen-1]=inorder[a];
            }
            root.right=buildTree(ap,ai);
            return root;
        }

    }

    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list=new ArrayList<>();
        if(root==null) return -1;
        visit(root.left,list);
        list.add(root.val);
        visit(root.right,list);
        return list.get(k-1);
    }

    private void visit(TreeNode root, List<Integer> list) {
        if(root==null) return;
        else {
            visit(root.left,list);
            list.add(root.val);
            visit(root.right,list);
        }
    }

    public int numIslands(char[][] grid) {
        int num=0;
        int H=grid.length;
        if(H<=0) return 0;
        int W=grid[0].length;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(grid[i][j]=='1'){
                    num++;
                    dfs(grid,i,j);
                }
            }
        }
        return num;
    }

    private void dfs(char[][] grid, int i, int j) {
        if(i>=0&&i<grid.length&&j>=0&&j<grid[0].length&&grid[i][j]=='1'){
            grid[i][j]='0';
            dfs(grid,i-1,j);
            dfs(grid,i,j-1);
            dfs(grid,i+1,j);
            dfs(grid,i,j+1);
        }
        return;
    }

}
